public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();

        String s1 = "abc";
        String s2 = "ef";
        System.out.println(test.longestCommonSubsequence(s1, s2));
    }

    public int longestCommonSubsequence(String text1, String text2) {
        /**
         * 最长公共子序列（两个数组的dp问题）
         * 状态表示：
         *  dp[i][j]表示 text1[0,i]范围 与 text2[0,j]范围，这两个范围中最长公共子序列的长度
         * 状态转移方程：
         *  我们对这两个范围的最后一个值进行判断
         *  if(text1.charAt(i) == text2.charAt(j)) {
         *      // 最后一个值相同，那么最长子序列一定包含这个值
         *      dp[i][j] = dp[i-1][j-1] + 1;
         *  } else {
         *      // 最后两个值不相同，那么最长子序列一定不包含这个值
         *      dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
         *  }
         * 初始化：
         *  由状态转移方程可得，我们在填写dp[i][j]处的元素时，会使用到i-1 和 j-1位置的值
         *  因此在填写第一行第一列是会出现数组越界访问的情况
         *  我们可以手动赋值，比较简单
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  返回dp[n-1][m-1]
         * */
        // 1 预处理
        int n = text1.length();
        int m = text2.length();
        // 2 创建dp表
        int[][] dp = new int[n][m];
        // 3 初始化
        for(int k = 0; k < n; k++) {
            if(text1.substring(0, k+1).contains(String.valueOf(text2.charAt(0)))) {
                dp[k][0] = 1;
            }
        }
        for(int k = 0; k < m; k++) {
            if(text2.substring(0, k+1).contains(String.valueOf(text1.charAt(0)))) {
                dp[0][k] = 1;
            }
        }
        // 4 填表
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(text1.charAt(i) == text2.charAt(j)) {
                    // 最后一个值相同，那么最长子序列一定包含这个值
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    // 最后两个值不相同，那么最长子序列一定不包含这个值
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        // 5 返回值
        return dp[n-1][m-1];
    }
}
